'''
@Author: shj
@Date: 2020-05-31 00:28:09
@LastEditTime: 2020-05-31 12:21:45
@LastEditors: shj
@Description:  用两个栈实现队列
@FilePath: /python3/algorithms/offer_code/5_Implement_queue_with_two_stacks.py
'''
'''
题目描述
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
'''
'''
思路
栈：FILO，队列：FIFO
push：将元素压入stack_1
pop: 将元素从stack_1压入stack_2,然后对stack_2执行pop

注意：stack_2压入元素的前提是stack_2为空，否则会出现队列乱序pop
    如果随时都可以往栈2里压，那么往栈1里压两个元素5、6（栈1状态是：{5,6}），马上出栈往栈2里压（栈2状态：{6,5}）；
    接着栈1又来了个元素7，栈2的元素5、6还没出栈，此时要是再把7压到栈2那么栈顶元素就变7了，没法先取出5；
    所以在往栈2压完一批元素后，栈1进了新的元素想往栈2压的时候，栈2必须把上一批的元素清空了才行(也就是栈2必须是空的)。
'''


class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def push(self, node):
        # write code here
        self.stack1.append(node)

    def pop(self):
        # return xx
        # stack2 为空时先压入元素，再pop
        if not (self.stack2):
            while self.stack1:
                self.stack2.append(self.stack1.pop())
            return self.stack2.pop()
        # stack2非空时直接pop
        return self.stack2.pop()